package RKUjava.math;

/** Implements a number of permutation algorithms. */
public class RKUPermutation 
{

  /** Permute an array according to Knuth's algorithm. This method calls
      permuteByKnuth(array,1);
      @param array The array to permute.
   */
  public static void permuteByKnuth(Object[] array)
    {
      permuteByKnuth(array,1);
    }

  /** Permute an array according to Knuth's algorithm. 
      <pre>
      while(shuffles>0) {
	&nbsp;&nbsp;for (i=array.length-1; i>=0; i--) {
	  &nbsp;&nbsp;&nbsp;&nbsp;j = RKURandom.randomInt(i+1);
	  &nbsp;&nbsp;&nbsp;&nbsp;// Swap entry i and j
	&nbsp;&nbsp;}
	shuffles--;
      }
      </pre>
      @param array The array to permute.
      @param shuffles The number of shuffle iterations. The time used to 
      permute is proportional to the number of shuffles.
   */
  public static void permuteByKnuth(Object[] array, int shuffles)
    {
      int i,j;
      Object tmp;

      while (shuffles>0) {
	for (i=array.length-1; i>=0; i--) {
	  j = RKURandom.randomInt(i+1);

	  // Swap two entries
	  tmp = array[i];
	  array[i] = array[j];
	  array[j] = tmp;
	}
	shuffles--;
      }

    }

  /** Permute an array according to variant 1 of Knuth's algorithm. 
      This method calls permuteArray1(array,1);
      @param array The array to permute.
   */
  public static void permuteArray1(Object[] array)
    {
      permuteArray1(array,1);
    }

  /** Permute an array according to variant 1 of Knuth's algorithm. 
      <pre>
      while(shuffles>0) {
        &nbsp;&nbsp;for (i=0; i&lt;array.length; i++) {
	&nbsp;&nbsp;&nbsp;&nbsp;j = RKURandom.randomInt(array.length);
  	&nbsp;&nbsp;&nbsp;&nbsp;// Swap entry i and j
	&nbsp;&nbsp;}
      }
      </pre>
      @param array The array to permute.
      @param shuffles The number of shuffle iterations. The time used to 
      permute is proportional to the number of shuffles.
   */
  public static void permuteArray1(Object[] array, int shuffles)
    {
      int i,j;
      Object tmp;

      while (shuffles>0) {
	for (i=0; i<array.length; i++) {
	  j = RKURandom.randomInt(array.length);

	  // Swap two entries
	  tmp = array[i];
	  array[i] = array[j];
	  array[j] = tmp;
	}
	shuffles--;
      }
    }

}
